<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.13"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>MRSL JPS3D Library: MRSL Jump Point Search Planning Library v1.1</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">MRSL JPS3D Library
   &#160;<span id="projectnumber">1.1</span>
   </div>
   <div id="projectbrief">An implementaion of Jump Point Search on 3D voxel map</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.13 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
$(function() {
  initMenu('',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
</div><!-- top -->
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">MRSL Jump Point Search Planning Library v1.1 </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p><a href="https://app.wercker.com/project/byKey/880ab5feaff25f0483e5f2c4f834b8c0"></a> </p><hr/>
<p> Jump Point Search for path planning in both 2D and 3D environments. Original jump point seach algorithm is proposed in <a href="https://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/download/3761/4007">"D. Harabor and A. Grastien. Online Graph Pruning for Pathfinding on Grid Maps. In National Conference on Artificial Intelligence (AAAI), 2011"</a>. The 3D version is proposed in <a href="http://ieeexplore.ieee.org/abstract/document/7839930/">"S. Liu, M. Watterson, K. Mohta, K. Sun, S. Bhattacharya, C.J. Taylor and V. Kumar. Planning Dynamically Feasible Trajectories for Quadrotors using Safe Flight Corridors in 3-D Complex Environments. ICRA 2017"</a>.</p>
<p>The distance map planner (<code><a class="el" href="classDMPlanner.html" title="Abstract base for planning. ">DMPlanner</a></code>) is also included in this repo. <code><a class="el" href="classDMPlanner.html" title="Abstract base for planning. ">DMPlanner</a></code> inflate a artificial potential field around obstacles and plan a safer path within a certain region. More detials are refered in the latter section.</p>
<h2>Installation</h2>
<h4>Required:</h4>
<ul>
<li>Eigen3</li>
<li>yaml-cpp</li>
</ul>
<p>Simply run following commands to install dependancy: </p><div class="fragment"><div class="line">$ sudo apt update</div><div class="line">$ sudo apt install -y libeigen3-dev libyaml-cpp-dev libboost-dev cmake</div></div><!-- fragment --><p>#### A) Simple cmake </p><div class="fragment"><div class="line">$ mkdir build &amp;&amp; cd build &amp;&amp; cmake .. &amp;&amp; make -j4</div></div><!-- fragment --><p>#### B) Using CATKIN </p><div class="fragment"><div class="line">$ mv jps3d ~/catkin_ws/src</div><div class="line">$ cd ~/catkin_ws &amp; catkin_make_isolated -DCMAKE_BUILD_TYPE=Release</div></div><!-- fragment --><h4>CTest</h4>
<p>Run following command in the <code>build</code> folder for testing the executables: </p><div class="fragment"><div class="line">$ make test</div></div><!-- fragment --><p>If everything works, you should see the results as: </p><div class="fragment"><div class="line">Running tests...</div><div class="line">Test project /home/sikang/thesis_ws/src/packages/jps3d/build</div><div class="line">    Start 1: test_planner_2d</div><div class="line">1/3 Test #1: test_planner_2d ..................   Passed    0.95 sec</div><div class="line">    Start 2: test_planner_3d</div><div class="line">2/3 Test #2: test_planner_3d ..................   Passed    0.00 sec</div><div class="line">    Start 3: test_distance_map_planner_2d</div><div class="line">3/3 Test #3: test_distance_map_planner_2d .....   Passed    1.26 sec</div><div class="line"></div><div class="line">100% tests passed, 0 tests failed out of 3</div><div class="line"></div><div class="line">Total Test time (real) =   2.22 sec</div></div><!-- fragment --><h4>Include in other projects</h4>
<p>Note that in other repository, add following commands in <code>CMakeLists.txt</code> in order to correctly link <code>jps3d</code>: </p><div class="fragment"><div class="line">find_package(jps3d REQUIRED)</div><div class="line">include_directories(${JPS3D_INCLUDE_DIRS})</div><div class="line">...</div><div class="line">add_executable(test_xxx src/test_xxx.cpp)</div><div class="line">target_link_libraries(test_xxx ${JPS3D_LIBRARIES})</div></div><!-- fragment --><p>Two libs will be installed: the standard <code>jps_lib</code> and a variation <code>dmp_lib</code>.</p>
<h2>JPS Usage</h2>
<p>To start a simple <code>JPS</code> planning thread: </p><div class="fragment"><div class="line">{c++}</div><div class="line">JPSPlanner2D planner(false); // Declare a 2D planner</div><div class="line">planner.setMapUtil(map_util); // Set collision checking function</div><div class="line">planner.updateMap(); // Set map, must be called before plan</div><div class="line">bool valid = planner.plan(start, goal, 1); // Plan from start to goal with heuristic weight 1, using JPS</div></div><!-- fragment --><p>First, the collision checking util must be loaded as: </p><div class="fragment"><div class="line">{c++}</div><div class="line">planner.setMapUtil(MAP_UTIL_PTR); // Set collision checking function</div></div><!-- fragment --><p> The <code>MAP_UTIL_PTR</code> can be either <code>JPS::OCCMapUtil</code> for 2D or <code>JPS::VoxelMapUtil</code> for 3D. It can be confusing to set up this util, see the example code for more details.</p>
<p>Second, call the function <code>updateMap()</code> to allocate the internal map: </p><div class="fragment"><div class="line">planner.updateMap(); // Set map, must be called before plan</div></div><!-- fragment --><p>Finally, call the function <code>plan</code> to plan a path from <code>start</code> to <code>goal</code>. The third input is the heuristic weight, the forth input indicates whether planning with <code>JPS</code> or <code>A*</code>. By default, the forth input is set to be <code>true</code>, means the <code>JPS</code> is the default back-end. To use normal <code>A*</code>: </p><div class="fragment"><div class="line">{c++}</div><div class="line">bool valid_astar = planner.plan(start, goal, 1, false); // Plan from start to goal with heuristic weight 1, using A*</div></div><!-- fragment --><p>Tow planners are provided for 2D and 3D map:</p><ul>
<li><code>JPSPlanner2D</code></li>
<li><code>JPSPlanner3D</code></li>
</ul>
<h4>Planning Example</h4>
<p>An example code for a 2D map is given in <a href="https://github.com/sikang/jps3d/blob/master/test/test_planner_2d.cpp"><code>test/test_planner_2d.cpp</code></a>, in which we plan from start to goal using both <code>A*</code> and <code>JPS</code>. The results are plotted in <a href="https://github.com/sikang/jps3d/blob/master/data/corridor.png">corridor.png</a>. Green path is from <code>A*</code>, red path is from <code>JPS</code>. Even though they are using two different routes and <code>JPS</code> is much faster, the distance/cost of two paths is the same. In other words, <code>JPS</code> guarantees the optimality but saves a significant amount of computation time.</p>
<div class="image">
<img src="corridor.png" alt="corridor.png"/>
<div class="caption">
Visualization</div></div>
<div class="fragment"><div class="line">$ ./build/test_planner_2d ../data/corridor.yaml</div><div class="line">start: 2.5  -2</div><div class="line">goal:  35 2.5</div><div class="line">origin:  0 -5</div><div class="line">dim: 799 199</div><div class="line">resolution: 0.05</div><div class="line">JPS Planner takes: 5.000000 ms</div><div class="line">JPS Path Distance: 35.109545</div><div class="line">JPS Planner takes: 5.000000 ms</div><div class="line">AStar Planner takes: 62.000000 ms</div><div class="line">AStar Path Distance: 35.109545</div></div><!-- fragment --><p>An example in 3D map is presented in <a href="https://github.com/sikang/jps3d/blob/master/test/test_planner_3d.cpp"><code>test/test_planner_3d.cpp</code></a> with the yaml <code>data/simple3d.yaml</code>.</p>
<h5>Mapping Example</h5>
<p>To generate map in <code>yaml</code> format which can be loaded directly in the test node, a simple executable file <a href="https://github.com/sikang/jps3d/blob/master/test/create_map.cpp"><code>test/create_map.cpp</code></a> is used. User can easily change the location of blocks in the source code.</p>
<h2>DMP Usage</h2>
<p><code><a class="el" href="classDMPlanner.html" title="Abstract base for planning. ">DMPlanner</a></code> stands for distance map planner which utilizes the artificial potential field to find a safer local path around a given path. We changed the API for setting map of <code><a class="el" href="classDMPlanner.html" title="Abstract base for planning. ">DMPlanner</a></code> in v1.1. The key feature of this planner is its ability to push the path away from obstacles as much as possible. An example is given in the following figure <a href="https://github.com/sikang/jps3d/blob/master/data/example_dmp.png">example_dmp.png</a>, where red path comes from <code>JPS</code> which is always attached to obstacles and blue path is derived from <code>DMP</code> which is much safer.</p>
<div class="image">
<img src="example_dmp.png" alt="example_dmp.png"/>
<div class="caption">
Visualization</div></div>
<p> The code for generating this figure is given in <a href="https://github.com/sikang/jps3d/blob/master/test/test_distance_map_planner_2d.cpp"><code>test/test_distance_map_2d.cpp</code></a>. </p><div class="fragment"><div class="line">$ ./build/test_distance_map_planner_2d ../data/corridor.yaml</div><div class="line">start: 2.5  -2</div><div class="line">goal:  35 2.5</div><div class="line">origin:  0 -5</div><div class="line">dim: 799 199</div><div class="line">resolution: 0.05</div><div class="line">JPS Planner takes: 7.000000 ms</div><div class="line">JPS Path Distance: 35.109545</div><div class="line">DMP Planner takes: 8.000000 ms</div><div class="line">DMP Path Distance: 37.186501</div></div><!-- fragment --><h2>Doxygen</h2>
<p>For more details, please refer to <a href="https://kumarrobotics.github.io/jps3d">Doxygen</a>. </p>
</div></div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.13
</small></address>
</body>
</html>
